package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/28/20 9:17 AM
 */
public class _188_买卖股票的最佳时机_IV {


    /**
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {

        if (prices == null || prices.length <= 0) {

            return 0;
        }

        if (k >= (prices.length >> 1)) {

            return infiniteCountMaxProfit(prices);
        }

        int len = (k<<1)|1;
        int[] dp = new int[len];

        for (int i = 0; i < len; i++) {

            if ((i & 1) == 1) {

                dp[i] = Integer.MIN_VALUE;
            }
        }

        for (int i = 0; i < prices.length; i++) {

            for (int j = 1; j < len; j++) {

                dp[j] = Math.max(dp[j], dp[j-1] + ((j&1)==1?-prices[i]:prices[i]));
            }
        }


        return dp[len - 1];
    }


    private int infiniteCountMaxProfit(int[] prices) {


        int noShares  = 0;
        int haveShares = -prices[0];

        for (int i = 1; i < prices.length; i++) {

            noShares = Math.max(noShares,haveShares + prices[i]);
            haveShares = Math.max(haveShares,noShares - prices[i]);
        }

        return noShares;
    }


}
